/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {

  let direction = [[0, -1], [1, 0], [0, 1], [-1, 0]], flag = false; // 代表上右下左
  let visited = new Array(board.length);
  for(let i = 0; i < visited.length; i++) {
    visited[i] = new Array(board[0].length).fill(false);
  }
  function dfs(depth, indexI, indexJ) {
    if(depth == word.length - 1) {
      flag = true;
      // console.log("visited", visited)
      return ;
    }
    // 上
    if(indexI - 1 >= 0 && !visited[indexI - 1][indexJ] && board[indexI - 1][indexJ] == word[depth + 1]) {
      visited[indexI - 1][indexJ] = true;
      dfs(depth + 1, indexI - 1, indexJ);
      visited[indexI - 1][indexJ] = false;
    }
    // 下
    if(indexI + 1 < board.length && !visited[indexI + 1][indexJ] && board[indexI + 1][indexJ] == word[depth + 1]) {
      visited[indexI + 1][indexJ] = true;
      dfs(depth + 1, indexI + 1, indexJ);
      visited[indexI + 1][indexJ] = false;
    }
    // 左
    if(indexJ - 1 >= 0 && !visited[indexI][indexJ - 1] && board[indexI][indexJ - 1] == word[depth + 1]) {
      visited[indexI][indexJ - 1] = true;
      dfs(depth + 1, indexI, indexJ - 1);
      visited[indexI][indexJ - 1] = false;
    }
    // 右
    if(indexJ + 1 < board[0].length && !visited[indexI][indexJ + 1] && board[indexI][indexJ + 1] == word[depth + 1]) {
      visited[indexI][indexJ + 1] = true;
      dfs(depth + 1, indexI, indexJ + 1);
      visited[indexI][indexJ + 1] = false;
    }
  }

  for(let i = 0; i < board.length; i++) {
    for(let j = 0; j < board[0].length; j++) {
      if(board[i][j] == word[0]) {
        visited[i][j] = true;
        dfs(0, i, j);
        visited[i][j] = false;
      }
    }
  }
  return flag;
};
let board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED";
console.log(exist(board, word));
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE";
console.log(exist(board, word));
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB";
console.log(exist(board, word));

